#include<iostream>
#include<cstring>
#include<vector>
#include<map>
#include<cstdio>
#include<algorithm>
#include<string>
#include<string.h>
#include<queue>
#include<math.h>
#include<set>
#include<functional>
using namespace std;
using ull = unsigned long long;
#define int long long
//using i128 = __int128_t;
inline int inc(int x, int v, int mod) { x += v;return x >= mod ? x - mod : x; }//代替取模+
#define endl '\n'
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 2e3 + 10, M = 1e5 + 10;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}





int lowbit(int x)
{
    return x & -x;
}

struct st
{
    int l,r,qs;
    bool operator<(const st& other) const {
        return qs < other.qs;
    }    
};



void solve()
{
    int n;
    cin >> n;
    int q;
    cin >> q;
    vector<int>arr(n + 10);
    vector<int>tree(n + 10);
    vector<st>asq(q + 10);
    vector<st>ask1(q + 10);
    map<st,int>ans;
    for(int i = 1; i <= n; i ++) cin >> arr[i];
    auto cmp = [&](const st& a1,const st& a2) -> bool
    {
        return arr[a1.qs] < arr[a2.qs];
        //return a1.qs < a2.qs;
    };

    for(int i = 1; i <= q; i ++)
    {
        cin >> asq[i].l >> asq[i].r >> asq[i].qs;
    }
    ask1 = asq;
    sort(asq.begin() + 1,asq.begin() + 1 + q,cmp);

    auto ask = [&](int x) -> int
    {
        int sum = 0;
        for(int i = x; i; i -= lowbit(i)) sum += tree[i];
        return sum;
    };

    auto add = [&](int x,int k){
        for(int i = x; i <= n; i += lowbit(i)) tree[i] += k;
    };
    int top = 1;
    // for(int i = 1; i <= q; i ++)
    // {
    //     cout << asq[i].l << ' ' << asq[i].r << ' ' << asq[i].qs << endl;
    // }
    for(int i = 1; i <= n; i ++)
    {
        add(arr[i],1);
        while(asq[top].qs == i) 
        {
            //cout << asq[top].qs << endl;
            int res = ask(asq[top].r) - ask(asq[top].l - 1);
            ans[asq[top]] = res;
            top++;
        }
    }
    for(int i = 1; i <= q; i ++)
    {
        //cout << ask1[i].l << ' ' << ask1[i].r << ' ' << ask1[i].qs << ' '; 
        cout << ans[ask1[i]] << endl;
    }

}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int tt;
    cin >> tt;
    //tt = 1;
    while (tt--)
    {
        solve();
    }
}